/**
 * Minimum Vertex Cover.
 *
 * <p>Given an undirected grap $G=(V,E)$, find the smallest set of vertices $S$ that cover all the edges (i.e. for any edge $(u,v)∈ E, u ∈ S \or v ∈ S$)
 *
 * <p>This problem is an NP-Complete problem. It's the opposite of independent set problem. If $S$ is a minimum vertex cover then $V \ S$ is the maximum independent set.
 *
 * <p><strong>Special cases.</strong>
 *
 * <p><u>Tree</u>: if a graph is a tree, it takes linear time to find the minimum coverage. The idea is there exists a minimum vertex cover set that does not include any leaf nodes. Assume a minimum vertex cover set includes some leaf nodes, we can remove these leaf nodes and add their parents instead. This new set will still be a minimum vertex cover.
 *
 * <p><u>Bipartite graph</u>: the minimum vertex cover of a bipartite is the opposite of maximum matching problem in bipartite. This can be solved in $O(mn)$ time using augmenting paths.
 *
 * <p><strong>Brute force.</strong>
 *
 * <p>Brute force will need to look at $2^n$ possible sets within $n$ vertices. This can be prohibitive for some large enough problem. If there exists a solution set $S$ where size $k$ of $S$ is small, we can formulate the problem differently with a different question: can we find a vertex cover with size of $k$? Then we take k = 1, 2, 3 ...
 *
 * <p>One technique to do brute force is to look at sub problem. $(u,v)$ be an edge of $G$, $G_u$ be the graph $G$ with vertex $u$ and all its edges removed. Then $G$ has minimum vertex cover of size $k$ ⇔ either $G_u$ or $G_v$ (or both) has minimum vertex cover of size $(k-1)$. The algorithm now becomes: given an integer $k$, select a random edge $(u,v)$, recursively find minimum vertex cover for $G_u$ and for $G_v$ with size $k-1$. This takes $O(2^k)$ recursive call, the total running time is $O(m2^k)$.
 *
 * <p><strong>Heuristics.</strong>
 *
 * <p><u>Greedy heuristic.</u> Algorithm: while the graph has edges, select a vertex with highest degree, add vertex to the result set, remove this vertex and all its edges. This algorithm can produce solution that is much worse than optimal solution.
 *
 * <p><u>List heuristics.</u>  Sort the vertices in descending order by degrees, iterate throgh the vertices in this order, if the vertex has edges, add it to the result, remove the vertex from the graph.
 *
 * <p><u>Integer Linear Programming.</u> This problem can be expressed as linear programming:
 * $$\table
 * \text"Minimize "   , ∑↙{v∈V} x_{v};
 * \text"subject to " , x_u+x_v ≥ 1, ∀ (u,v) ∈ E;
 *                    , x_{v} ∈ \{0,1\}, ∀ u ∈ V; 
 *                    $$
 *
 * <p><u>Maximal matching.</u> 
 *
 * http://www.cse.cuhk.edu.hk/~chi/csc5160-2008/notes/L15-cover.pdf
 * http://cgm.cs.mcgill.ca/~avis/courses/360/notes/vertexcover.pdf
 *
 *
 * @author Trung Phan
 *
 */
package net.tp.algo.cover;
